package dijkstra;

import java.util.ArrayList;


class Graph
{
	public static int MAX=999;
	int numNode;
	int[][] adjacent;
	boolean[] S;
	int[] d; 
	int[] prev;
	
	public Graph() {
		
	}
	public Graph(int n)
	{
		numNode = n;
	}
	
	public void init()
	{
		this.d = new int[this.numNode];
		this.S = new boolean[this.numNode];
		this.prev = new int[this.numNode];

		for(int i = 0 ; i < this.d.length; ++i)
		{
			this.d[i] = MAX;
			this.S[i] = false;
			this.prev[i] = -1;
		}

		adjacent = new int[numNode][numNode];
		for(int i = 0 ; i < numNode; ++i )
		{
			for (int j = 0 ; j < numNode; ++j )
			{
				adjacent[i][j] = MAX;
			}
		}
	}
	
	public void printMatrix( )
	{
		System.out.format("    ");
		for(int i = 0 ; i  < numNode; ++i )
		{
			System.out.format("%4d", i);
		}
		System.out.println();
		for(int i = 0 ; i < numNode; ++i )
		{
			System.out.format("%4d", i);
			for(int j = 0 ; j < numNode; ++j)
			{
				if ( adjacent[i][j] != MAX)
					System.out.format("%4d", adjacent[i][j] );
				else
					System.out.print("    ");
			}
			System.out.println();
		}
		
	}
	
	public void insertNode(int i, int j, int w)
	{
		this.adjacent[i][j] = w;
	}
	public void setAdjecent(int[][] m)
	{
		this.numNode  = m.length;
		this.init();
		this.adjacent = m;

	}
	
	public void findShortestPath(int start_node, int end_node)
	{
		this.d[start_node] = 0;
		int t = -1;
		while( true )
		{
			int u = -1;
			int min = MAX;
			for(int i = 0; i < this.numNode; ++i )
			{
				if ( this.S[i] == false && this.d[i] < min )
				{
					min = this.d[i];
					u = i;
				}
			}
			if ( u == end_node) {
				System.out.println(this.d[end_node]);
				System.out.println("경로:");
				while(u != start_node ) {
					System.out.format("%d <- ", u);
					u = prev[u];
				}
				System.out.format("%d", start_node);
				break;
			}
			if ( u == -1 ) {
				System.out.println("Not reached");
				break;
			}
			this.S[u] = true;
			
			for (int v = 0; v < this.numNode; ++v)
			{
				if ( this.adjacent[u][v] != MAX && d[v] > d[u] + this.adjacent[u][v] )
				{
					d[v] = d[u] + this.adjacent[u][v];
					prev[v] = u;
				}
			}
			
		}
	}

}
public class Main {
	
	public static int[][] matrix1 = { 
		//  0    1    2    3    4    5
		{ 999,  50,  45,  10, 999, 999 }, // 0 
		{ 999, 999,  10,  15, 999, 999 }, // 1 
		{ 999, 999, 999, 999,  30, 999 }, // 2 
		{  20, 999, 999, 999,  15, 999 }, // 3
		{ 999,  20,  35, 999, 999, 999 }, // 4
		{ 999, 999, 999, 999,   3, 999 }  // 5
		};
	
	
	public static void test2()
	{
		Graph g = new Graph(7);
		g.init();
		g.insertNode(0, 1, 14);
		g.insertNode(0, 3, 22);
		g.insertNode(0, 4, 4);
		g.insertNode(1, 6, 3);
		g.insertNode(2, 1, 16);
		g.insertNode(2, 3, 12);
		g.insertNode(4, 3, 12);
		g.insertNode(4, 5, 10);
		g.insertNode(6, 5, 1);
		g.findShortestPath(0, 5);
		
	}

	public static void main(String[] args)
	{
		/*
		Scanner scanner = new Scanner(System.in);
		System.out.print("전체 노드 개수: ");
		int N = scanner.nextInt();
		System.out.print("간선 개수: ");
		int E = scanner.nextInt(); 
		Graph g = new Graph(N);
		for( int i = 0 ; i < E; ++i )
		{
			System.out.format("%d번째 간선 (u, v, w) 정보: ", i);
			int u = scanner.nextInt();
			int v = scanner.nextInt();
			int w = scanner.nextInt();
			g.insertNode(u, v, w);
		}
		g.printMatrix();
		*/
		
		/*
		Graph g = new Graph();
		g.setAdjecent(matrix1);
		g.printMatrix();
		g.findShortestPath(3, 2);
		*/
		test2();
	}


}
